Safety in terms of collision avoidance for multi-robot systems is a difficult challenge under uncertainty, non-determinism, and lack of complete information. This paper aims to propose a collision avoidance method that accounts for both measurement uncertainty and motion uncertainty. In particular, we propose Probabilistic Safety Barrier Certificates (PrSBC) using Control Barrier Functions to define the space of admissible control actions that are probabilistically safe with formally provable theoretical guarantee. By formulating the chance constrained safety set into deterministic control constraints with PrSBC, the method entails minimally modifying an existing controller to determine an alternative safe controller via quadratic programming constrained to PrSBC constraints. The key advantage of the approach is that no assumptions about the form of uncertainty are required other than finite support, also enabling worst-case guarantees. We demonstrate effectiveness of the approach through experiments on realistic simulation environments.

Beyond the strong support from R4, all reviewers recommend acceptance. Still, the reviewers raise some concerns that the authors should clarify for future versions of the paper, such as R1's concerns about the per-timestep basis of the high-probability guarantees allowing for high chances of failure in the long term. A reviewer also raises the question of whether NeurIPS is an appropriate venue for this work. Given the emphasis on safe reinforcement learning and the many methods in that field that try to tackle similar problems, this paper seems relevant and of interest to the NeurIPS community despite the control theory / non-learning nature of the proposed solution.

Weaknesses: While the methodology is overall quite sound, I am unsure about two main points: (1) The overall approach is to gradually reduce the various forms of variability in the problem. So, for instance, we start with a chance constraint formulation which point-wise and pair-wise delineates the concerns of collision-avoidance. Then, we have a specific protocol for turning the problem into a decentralised form, etc. All this limits the expressivity of the overall framework. So, for instance, if the overall constraint were not just collision avoidance - say, we had a max restriction on numbers of agents allowed within a volume (timely, as I write this review!)

Safety in terms of collision avoidance for multi-robot systems is a difficult challenge under uncertainty, non-determinism, and lack of complete information. This paper aims to propose a collision avoidance method that accounts for both measurement uncertainty and motion uncertainty. In particular, we propose Probabilistic Safety Barrier Certificates (PrSBC) using Control Barrier Functions to define the space of admissible control actions that are probabilistically safe with formally provable theoretical guarantee. By formulating the chance constrained safety set into deterministic control constraints with PrSBC, the method entails minimally modifying an existing controller to determine an alternative safe controller via quadratic programming constrained to PrSBC constraints. The key advantage of the approach is that no assumptions about the form of uncertainty are required other than finite support, also enabling worst-case guarantees.